// #include <stdio.h>

// int Factorial(int n);

// int main(void)
// {
//     int n = 0;
//     int sum = 0;

//     scanf ("%d", &n);
//     while (n > 0)
//     {
//         sum += Factorial(n);
//         --n;
//     }
//     printf("%d\n", sum);

//     return 0;
// }

// int Factorial(int n)
// {
//     if (n == 1)
//     {
//         return 1;
//     }
//     else
//     {
//         return n * Factorial(n - 1);
//     }
// }

// #include <stdio.h>

// int main(void)
// {
//     int i = 0;
//     int j = 0;
//     int ret = 1;
//     int sum = 0;

//     for (i = 0; i < 10; ++i)
//     {
//         ret = 1;
//         for (j = 1; j <= 10; ++j)
//         {
//             ret *= j;
//         }
//         sum += ret;
//     }
//     printf("%d\n", sum);
    
//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int i = 0;
//     int ret = 1;
//     int sum = 0;

//     for (i = 1; i <= 10; ++i)
//     {
//         ret *= i;
//         sum += ret;
//     }

//     printf("%d\n", sum);
//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//     int left = 0;
//     int right = sizeof(arr) / sizeof(arr[0]) - 1;
//     int mid = 0;
//     int key = 7;

//     while (left <= right)
//     {
//         mid = (left + right) / 2;
//         if (arr[mid] < key)
//         {
//             left = mid + 1;
//         }
//         else if (arr[mid] > key)
//         {
//             right = mid - 1;
//         }
//         else
//             break;
//     }
//     if (left <= right)
//     {
//         printf("%d\n", mid);
//     }
//     else
//     {
//         printf("没找到");
//     }
//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int i = 1;                  //1.初识化

//     while (i <= 10)             //2.判断
//     {
//         printf("%d ", i);
//         ++i;                    //3.调整
//     }

//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int i = 0;

//     //表达式1: i = 1   初始化
//     //表达式2: i <= 10  条件判断 判断为真执行循环语句
//     //表达式3: ++i     调整 
//     for (i = 1; i <= 10; ++i)
//     {
//         printf("%d ", i);
//     }

//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int i = 0;

//     for (i = 1; i <= 10; ++i)
//     {
//         if (5 == i)
//         {
//             continue;
//         }
//         printf("%d ", i);
//     }

//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     for(;;)
//     {
//         printf("hehe\n");
//     }

//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int i = 0;
//     int j = 0;

//     for (i = 0; i < 4; ++i)
//     {
//         for (j = 0; j < 4; ++j)
//         {
//             printf("hehe\n");
//         }
//     }
//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int x, y;

//     for (x = 0, y = 0; x<2 && y<5; ++x, y++)
//     {
//         printf("hehe\n");
//     }

//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int i = 0;
//     int j = 0;

//     for (i = 0, j = 0; j = 0; ++i, ++j)
//     {
//         ++j;
//     }

//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int i = 1;
//     do
//     {
//         if(5 == i)
//             continue;
//         printf("%d ", i);
//         ++i;
//     } while (i <= 10);
    

//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int n = 0;
//     int ret = 1;

//     scanf("%d", &n);
//     while (n > 0)
//     {
//         ret *= n;
//         --n;
//     }
//     printf("%d\n", ret);

//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int n = 10;
//     int ret = 1;
//     int sum = 0;
//     int i = 0;
//     int j = 0;

//     for (i = 1; i <= n; ++i)
//     {
//         ret = 1;
//         for (j = 1; j <= i; ++j)
//         {
//             ret *= j;
//         }
//         sum += ret;
//     }
//     printf("%d\n", sum);

//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int n = 10;
//     int ret = 1;
//     int sum = 0;
//     int i = 0;

//     for (i = 1; i <= n; ++i)
//     {
//         ret *= i;
//         sum += ret;
//     }
//     printf("%d\n", sum);

//     return 0;
// }

// #include <stdio.h>

// int main(void)
// {
//     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};    //定义有序数组
//     int key = 7;                                    //待查找的值
//     int len = 0;                                    //存放数组长度
//     int i = 0;
    
//     len = sizeof(arr) / sizeof(arr[0]);             //得到数组长度
    
//     //遍历数组得到对应值的索引
//     for (i = 0; i < len; ++i)   
//     {                    
//         if (arr[i] == key)
//         {
//             break;
//         }
//     }
    
//     //如果i == len,则表示没查找到
//     //如果i < len,则表示查找到了
//     if(i == len)
//     {
//         printf("没有该值\n");
//     }
//     else if (i < len)
//     {
//         printf("%d\n", i);
//     }

//     return 0;
// }

// #include <stdio.h>

// int BinarySearch(int arr[], int size, int key);

// int main(void)
// {
//     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};    //定义有序数组
//     int key = 7;                                    //待查找的值
//     int size = sizeof(arr) / sizeof(arr[0]);        //存放数组长度
//     int result = 0;                                 //存放结果

//     result = BinarySearch(arr, size, key);
//     if (result == -1)
//     {
//         printf("未找到\n");
//     }
//     else
//     {
//         printf("%d", result);
//     }

//     return 0;
// }

// /*
// 函数内容:对有序数组进行二分查找
// 输入参数:1.arr[] 有序数组名 2.size 数组的大小 3.key 待查找的值
// 输出参数:查找结果
// 返回值:若查到,返回该值索引;若没有,返回-1
// */
// int BinarySearch(int arr[], int size, int key)
// {
//     int left = 0;                                   //查找范围最左的索引
//     int right = size - 1;                           //查找范围最右的索引
//     int mid = 0;                                    //中间位置

//     while (left <= right)
//     {
//         mid = (left + right) / 2;                   //计算mid的值
//         if (arr[mid] == key)                        
//         {
//             return mid;                             //找到直接返回索引
//         }
//         else if (arr[mid] > key)
//         {
//             right = mid - 1;                        //比key大 right - 1
//         }
//         else if (arr[mid] < key)
//         {
//             left = mid + 1;                         //比key小 left + 1
//         }
//     }
//     return -1;                                      //代码运行到这说明没有找到,返回-1
// }

// #include <stdio.h>
// #include <string.h>
// #include <windows.h>

// int main(void)
// {
//     char arr1[] = "###############";
//     char arr2[] = "Hello  World!!!";
//     int left = 0;
//     int right = strlen(arr1) - 1;
    
//     while (left <= right)
//     {
//         arr1[left] = arr2[left];
//         arr1[right] = arr2[right];
//         printf("%s\n", arr1);
//         Sleep(1000);                    //单位是毫秒
//         system("cls");                   //清理屏幕
//         ++left;
//         --right;
//     }

//     return 0;
// }

// #include <stdio.h>
// #include <string.h>

// int main(void)
// {
//     //假定密码是123456
//     char password[20] = {0,};               //存放输入的密码
//     int i = 0;
//     int flag = 0;                           //密码正确为1, 三次均错误为0

//     for (i = 0; i < 3; ++i)
//     {
//         printf("请输入密码:");
//         scanf("%s", password);

//         if (strcmp(password, "123456") == 0)
//         {
//             flag = 1;
//             break;
//         }
//         else
//         {
//             printf("输入错误.\n");
//         }
//     }
//     if (flag == 1)
//     {
//         printf("登陆成功\n");
//     }
//     else
//     {
//         printf("三次输入失败,登陆失败.\n");
//     }
    
//     return 0;
// }

//在屏幕上输出9*9乘法口诀表

// #include <stdio.h>

// int main(void)
// {
//     int i = 0;
//     int j = 0;

//     for (i = 1; i <= 9; ++i)
//     {
//         for (j = 1; j <= i; ++j)
//         {
//             printf("%d*%d=%d\t", j, i, i * j);
//         }
//         printf("\n");
//     }
//     return 0;
// }

//求10 个整数中最大值

// #include <stdio.h>

// int main(void)
// {
//     int arr[10] = {0,};                 
//     int max = 0;
//     int i = 0;
//     int size = sizeof(arr) / sizeof(arr[0]);

//     printf("Please input 10 (int) numbers:\n");
//     for (i = 0; i < size; ++i)
//     {
//         scanf("%d", &arr[i]);
//     }

//     max = arr[0];
//     for (i = 1; i < size; ++i)
//     {
//         if (arr[i] > max)
//         {
//             max = arr[i];
//         }
//     }
//     printf("Max = %d\n", max);

//     return 0;
// }

//计算1/1-1/2+1/3-1/4+1/5 …… + 1/99 - 1/100 的值，打印出结果

// #include <stdio.h>

// int main(void)
// {
//     double ret = 0.0;
//     double sum = 0.0;
//     int i = 0;

//     for (i = 1; i <= 100; ++i)
//     {
//         ret = (i % 2 != 0) ? (1.0/i) : (-1.0/i);
//         sum += ret;
//     }
//     printf("%lf\n", sum);

//     return 0;
// }

//编写程序数一下 1到 100 的所有整数中出现多少个数字9

// #include <stdio.h>

// int main(void)
// {
//     int i = 0;
//     int count = 0;                      //存储个数
//     int last = 0;                       //存储每个数的个位
//     int num = 0;

//     for (i = 1; i <= 100; ++i)
//     {
//         num = i;
//         while (num)
//         {
//             last = num % 10;
//             num /= 10;
//             if (9 == last)
//             {
//                 ++count;
//                 break;
//             }
//         }
//     }
//     printf("%d\n", count);

//     return 0;
// }

/*
编写代码在一个整形有序数组中查找具体的某个数

要求：找到了就打印数字所在的下标，找不到则输出：找不到。
*/

#include <stdio.h>

int BinarySearch(int arr[], int left, int right, int key);

int main(void)
{
    int arr[] = {1, 2, 4, 6, 7, 8, 9, 10, 11, 16};
    int key = 0;
    int result = 0;
    int left = 0;
    int right = sizeof(arr) / sizeof(arr[0]) - 1;

    scanf("%d", &key);
    result = BinarySearch(arr, left, right, key);
    if (result == -1)
    {
        printf("没找到.\n");
    }
    else
    {
        printf("%d\n", result);
    }

    return 0;
}

//递归版本的二分查找
int BinarySearch(int arr[], int left, int right, int key)
{
    if (left > right)
    {
        return -1;
    }
    int mid = (left + right) / 2;
    if (arr[mid] == key)
    {
        return mid;
    }
    else if(arr[mid] < key)
    {
        return BinarySearch(arr, mid+1, right, key);
    }
    else if(arr[mid] > key)
    {
        return BinarySearch(arr, left, mid-1, key);
    }
}